import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class BirrayTree {
    class TreeNode{
        public char val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(char val){
            this.val = val;
        }
    }

    public TreeNode createTree() {
        TreeNode a = new TreeNode('A');
        TreeNode b = new TreeNode('B');
        TreeNode c = new TreeNode('C');
        TreeNode d = new TreeNode('D');
        TreeNode e = new TreeNode('E');
        TreeNode f = new TreeNode('F');
        TreeNode g = new TreeNode('G');
        TreeNode h = new TreeNode('H');
//
        a.left = b;
        a.right = c;
        b.left = d;
        b.right = e;
        e.right = h;
        c.right = g;
        c.left = f;

        return a;
    }

    public String tree2str(TreeNode root) {
        if(root == null){
            return null;
        }
        StringBuilder str = new StringBuilder();
        tree2strChild(root,str);
        return str.toString();
    }
    public void tree2strChild(TreeNode root,StringBuilder str){
        if(root == null){
            return;
        }
        str.append(root.val);
        if(root.left != null){
            str.append("(");
            tree2strChild(root.left,str);
            str.append(")");
        }else {
            if(root.right == null){
                return;
            }else{
                str.append("()");
            }
        }

        if(root.right != null){
            str.append("(");
            tree2strChild(root.right,str);
            str.append(")");
        }else {
            return;
        }
    }

    public void postOrder(TreeNode root){
        if(root == null){
            return;
        }

        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode tmp = null;

        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.peek();
            if (top.right == null || tmp == top.right) {
                System.out.print(top.val + " ");
                stack.pop();
                tmp = top;
            } else {
                cur = top.right;
            }
        }
    }

    public List<Character> postorderTraversal(TreeNode root){
        List<Character> list = new ArrayList<>();
        if(root == null){
            return list;
        }

        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode tmp = null;

        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.peek();
            if (top.right == null || tmp == top.right) {
                list.add(top.val);
                stack.pop();
                tmp = top;
            } else {
                cur = top.right;
            }
        }
        return list;
    }




}
